package com.lishem.carl._04string;

/**
 * https://leetcode.cn/problems/repeated-substring-pattern/description/
 * <p>
 * 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
 * <p>
 * 示例 1:
 * <p>
 * 输入: s = "abab"
 * <p>
 * 输出: true
 * <p>
 * 解释: 可由子串 "ab" 重复两次构成。
 * <p>
 * 示例 2:
 * <p>
 * 输入: s = "aba"
 * <p>
 * 输出: false
 * <p>
 * 示例 3:
 * <p>
 * 输入: s = "abcabcabcabc"
 * <p>
 * 输出: true
 * <p>
 * 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
 */
public class _7LetCode459_重复的子字符串 {

    public boolean repeatedSubstringPattern(String s) {
        char[] chars = s.toCharArray();
        int[] next = new int[chars.length + 1];
        next[0] = -1;
        next[1] = 0;
        int pos = 2;
        int cn = 0;
        while (pos != next.length) {
            if (chars[pos - 1] == chars[cn]) {
                next[pos++] = ++cn;
            } else if (next[cn] == -1) {
                next[pos++] = 0;
            } else {
                cn = next[cn];
            }
        }
        return next[chars.length] != 0 && chars.length % (chars.length - next[next.length - 1]) == 0;
    }

    public static void main(String[] args) {
        _7LetCode459_重复的子字符串 sol = new _7LetCode459_重复的子字符串();
        System.out.println(sol.repeatedSubstringPattern("abac"));
        System.out.println(sol.repeatedSubstringPattern("abab"));
        System.out.println(sol.repeatedSubstringPattern("aba"));
        System.out.println(sol.repeatedSubstringPattern("abcabcabcabc"));
    }
}